// 示例 1：
// 输入: s = "leetcode", wordDict = ["leet", "code"]
// 输出: true
// 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
// 示例 2：
// 输入: s = "applepenapple", wordDict = ["apple", "pen"]
// 输出: true
// 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
// 注意，你可以重复使用字典中的单词。
// 示例 3：
// 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
// 输出: false

s = "leetcode", wordDict = ["leet", "code"]

var wordBreak = function (s, wordDict) {
    const len = s.length;
    const dp = new Array(len + 1).fill(false); // dp[i] 表示前i个字符是否能被拆分
    const wordSet = new Set(wordDict); // 使用 Set 替代对象，更规范

    dp[0] = true; // 空字符串可拆分

    for (let i = 1; i <= len; i++) {
        for (let j = 0; j < i; j++) { // 关键修正：j 从 0 开始
            if (dp[j] && wordSet.has(s.slice(j, i))) {
                dp[i] = true;
                break; // 找到一种拆分方式即可
            }
        }
    }

    return dp[len];
};

console.log(wordBreak(s, wordDict));
